package com.leetcode.根据算法进行分类.二分查找相关;

/**
 * @author: xiaomi
 * @date: 2021/3/30
 * @description: 74. 搜索二维矩阵
 * https://leetcode-cn.com/problems/search-a-2d-matrix/
 */
public class B_74_搜索二维矩阵 {

    static B_74_搜索二维矩阵 action = new B_74_搜索二维矩阵();

    public static void main(String[] args) {
        test1();
    }

    static void test1() {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int target = 3;
        boolean res = action.searchMatrix(matrix, target);
        System.out.println("res = " + res);
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int size = m * n;
        int begin = 0, end = size, mid = size >> 1;
        //[)
        while (begin < end) {
            int comp = compare(mid, matrix, m, n, target);
            switch (comp) {
                case 0:
                    return true;
                case -1:
                    begin = mid + 1;
                    break;
                default:
                    end = mid;
                    break;
            }
            mid = begin + ((end - begin) >> 1);

        }
        return false;
    }


    private int compare(int mid, int[][] matrix, int m, int n, int target) {
        int i = mid / n;
        int j = mid % n;
        if (matrix[i][j] == target) {
            return 0;
        } else if (matrix[i][j] < target) {
            return -1;
        } else {
            return 1;
        }
    }


}
